package bit;

/**
 * 题目：就某个浮点数值的n次方
 * y: x的n次方
 *
 * @Author Gavin
 * @date 2021.12.08 22:58
 */
public class bit_2 {
    /**
     * 思路：
     * 1. 使用for循环n次，然后根据n的正负值返回，这种方式效率就是比较低
     * 2.使用二进制的方式来处理，效率变为O(log(n))
     * 因为次方就是二进制2的倍数关系，这里就比较巧妙了
     */

    //该方式效率比较低
    //Time:O(n) Space:O(1)
    public static double solution1(double x, int n) {
        double result = 1;
        long N = Math.abs((long) n);
        for (int i = 0; i < n; i++) {
            result = result * x;
        }
        return n < 0 ? 1 / result : result;
    }

    //二进制位来处理

    /**
     * 比如求2的11次方
     * 11 的二进制位表示位： 1 0 1 1   X^8*X^4*X^2*X^1
     * 2的11次方可以表示为：   2^8*2^2*2^1  这里面的8，2，1分别对应上面二进制上面相应位上的值
     */
    //Time:O(log(n)) Space:O(1)
    public static double solution(double x, int n) {
        double result = 1;
        long N = Math.abs((long) n);
        while (N != 0) {
            if ((N & 1) == 1) result *= x;
            x *= x;//巧妙点，此时x的值要变为原来的平方大小。
            N >>= 1;//这里也是巧妙的地方，二进制位向右移动一位说明x要乘以原来的x才能对应值的大小(变为两倍)
        }
        return n < 0 ? 1 / result : result;
    }
}
